package com.cat.greedyAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/partition-labels/description/?envType=problem-list-v2&envId=greedy
 * @create 2025/10/3 18:45
 * @since JDK17
 */

public class Solution46 {
    public List<Integer> partitionLabels(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        List<Integer> ans = new ArrayList<>();
        int[] h = new int[128], v = new int[128];
        for (int i = 0; i < n; i++) {   // 记录所有的字符最后一个出现的位置
            h[arr[i]] = i;
        }

        for (int i = 0; i < n; i++) {
            int start = i, end = h[arr[i++]];
            while (i < end) {
                end = Math.max(end, h[arr[i++]]);
            }
            ans.add(end - start + 1);
        }

        return ans;
    }
}
